#include <iostream>
using namespace std;

template <class T>
void swap(T &x1,T &x2)
{
	T k = x1;
	x1 = x2;
	x2 = k;
}

template <class T>
class Sort
{
	void BubbleSort(vector<T>& nums, int n)
	{
		for (int i = 0; i < n; i++)
		{
			bool tf = ture;
			for (int j = 0; j < n - i; j++)
			{
				if (nums[i] > nums[j])
				{
					swap(nums[i], nums[j]);
					tf = false;
				}
			}
			if (tf)
			{
				break;
			}
		}
	}

	T my_mid(vector<T>& nums, int left, int right)
	{
		int mid = (left + right) / 2;
		if (nums[left] < nums[mid])
		{
			if (nums[left] > nums[right])
			{
				return left;
			}
			if (nums[right] < nums[mid])
			{
				return mid;
			}
		}
		if (nums[left] > nums[mid])
		{
			if (nums[left] < nums[right])
			{
				return left;
			}
			if (nums[right] < nums[mid])
			{
				return mid;
			}
		}
		return right;
	}

	void QuickSort1(vector<T>& nums, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		swap(nums[left], nums[my_mid(left, right)])
			T poke = nums[left];
		while (left < right)
		{
			while (left < right && nums[right] >= poke)
			{
				right--;
			}
			nums[left] = nums[right];
			while (left < right && nums[left] = < poke)
			{
				left++;
			}
			nums[right] = nums[left];
		}
		nums[left] = poke;
		QuickSort1(nums, 0, left - 1);
		QuickSort1(nums, left + 1, right);
	}

	void QuickSort1(vector<T>& nums, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		swap(nums[left], nums[my_mid(left, right)])
			T poke = nums[left];
		while (left < right)
		{
			while (left < right && nums[right] >= poke)
			{
				right--;
			}
			nums[left] = nums[right];
			while (left < right && nums[left] = < poke)
			{
				left++;
			}
			nums[right] = nums[left];
		}
		nums[left] = poke;
		QuickSort1(nums, 0, left - 1);
		QuickSort1(nums, left + 1, right);
	}

	void QuickSort2(vector<T>& nums, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		swap(nums[left], nums[my_mid(left, right)])
			T poke = nums[left];
		while (left < right)
		{
			while (left < right && nums[right] >= poke)
			{
				right--;
			}
			while (left < right && nums[left] = < poke)
			{
				left++;
			}
			swap(nums[left], nums[right]);
		}
		nums[left] = poke;
		QuickSort2(nums, 0, left - 1);
		QuickSort2(nums, left + 1, right);
	}

	void QuickSort3(vector<T>& nums, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		swap(nums[left], nums[my_mid(left, right)])
			T poke = nums[left];
		int slow = left - 1;
		int fast = left;
		while (fast <= right)
		{
			if (nums[fast] < poke)
			{
				fast++;
			}
			else
			{
				slow++;
				swap(nums[slow], nums[fast]);
				fast++;
			}
		}
		nums[slow] = poke;
		QuickSort3(nums, 0, slow - 1);
		QuickSort3(nums, slow + 1, right);
	}

	void ShellSort(vector<T>& nums, int n)
	{
		int p = n / 2;
		while (p)
		{
			for (int i = 0; i < n - p; i += p)
			{
				T grep = nums[i + p];
				int k = i;
				while (k >= 0)
				{
					if (nums[k] > nums[k + p])
					{
						nums[k + p] = nums[k];
						k -= p;
					}
					else
					{
						break;
					}
				}
				nums[k + p] = grep;
			}
		}
	}

	void InsertSort(vector<T>& nums, int n)
	{
		for (int i = 0; i < n - 1; i++)
		{
			T grep = nums[i + 1];
			int k = i;
			while (k >= 0)
			{
				if (nums[k] > nums[k + 1])
				{
					nums[k + 1] = nums[k];
					k--;
				}
				else
				{
					break;
				}
			}
			nums[k + 1] = grep;
		}
	}

	void SelectSort(vector<T>& nums, int n)
	{
		int left = 0;
		int right = n - 1;
		while (left < right)
		{
			T my_max = right;
			T my_min = left;
			for (int i = left; i <= right; i++)
			{
				if (nums[i] > nums[my_max])
				{
					my_max = i;
				}
				if (nums[i] < nums[my_min])
				{
					my_min = i;
				}
				swap(nums[left], nums[my_min]);
				swap(nums[right], nums[my_max]);
				if (my_max = left)
				{
					swap(nums[my_min], nums[right]);
				}
			}
			left++;
			right--;
		}
	}
	void BigHeap(vector<T> nums, int parent, int n)
	{
		int child = parent * 2 + 1;
		while (child < n)
		{
			if (child + 1 < n && nums[child + 1] > nums[child])
			{
				child++;
			}
			if (nums[child] > nums[parent])
			{
				swap(nums[child], nums[parent]);
			}
			parent = child;
			child = parent * 2 + 1;
		}
	}

	void HeapSort(vector<T>& nums, int n)
	{
		for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		{
			BigHeap(nums, i, n);
		}
		int end = n - 1;
		while (end)
		{
			swap(nums[end], nums[0]);
			BigHeap(nums, 0, end);
			end--;
		}
	}

	void _MergeSort(vector<T> nums, vector<T> ret, int left, int right)
	{
		if (left >= right)
		{
			return;
		}
		int mid = (left + right) / 2;
		_MergeSort(nums, ret, left, mid - 1);
		_MergeSort(nums, ret, mid, right);
		int begin1 = left;
		int begin2 = mid + 1;
		int index = left;
		while (begin1 <= mid && begin2 <= right)
		{
			if (nums[begin1] < nums[begin2])
			{
				ret[index++] = nums[begin1++];
			}
			else
			{
				ret[index++] = nums[begin2++];
			}
		}
		while (begin1 <= mid)
		{
			ret[index++] = nums[begin1++];
		}
		while (begin2 <= right)
		{
			ret[index++] = nums[begin2++];
		}
		for (int i = left; i <= right; i++)
		{
			nums[i] = ret[i];
		}
	}

	void MergeSort(vector<T> nums, int n)
	{
		vector<T> ret(n);
		_MergeSort(nums, ret, 0, n - 1);
	}
};